package com.mlamp.动态规划;

public class 最长公共子序列 {
    public static void main(String[] args) {
        String s1 = "zabcde", s2 = "acez";
        //int result = longestCommonSubsequence("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA ", "GTCGTTCGGAATGCCGTTGCTCTGTAAA");
        //int result = longestCommonSubsequence("android", "random");
        int result = longestCommonSubsequence(s1, s2);
        System.out.println(result);
        String res = "GTCGTCGGAAGCCGGCCGAA";
        System.out.println(res.length());

    }

    private static final int longestCommonSubsequence(String s1, String s2) {
        StringBuilder sb = new StringBuilder();
        int length1 = s1.length();
        int length2 = s2.length();
        char[] chars = s1.toCharArray();
        char[] chars1 = s2.toCharArray();

        int[][] dp = new int[length1 + 1][length2 + 1];
//        for (int i = 0; i <= length2; i++) {
//            dp[0][i] = 0;
//        }
//
//        for (int i = 0; i <= length1; i++) {
//            dp[i][0] = 0;
//        }

        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (chars[i - 1] == chars1[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        //System.out.println(sb.toString());
        for (int i = 0; i <= length1; i++) {
            for (int j = 0; j <= length2; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }


        for (int i = 0; i <= length1; i++) {
            for (int j = 0; j <= length2; j++) {
                if (i > 0 && j > 0) {
                    if (dp[i][j] > dp[i - 1][j] && dp[i][j] > dp[i][j - 1]) {
                        if (valid(dp, length1 + 1, length2 + 1, i, j)) {
                            sb.append(chars[i - 1]);
                        }
                    }
                }
            }
        }
        System.out.println(sb.toString());
        return dp[length1][length2];
    }

    private static boolean valid(int[][] dp, int row, int col, int i, int j) {
        int val = dp[i][j];
        for (int k = i + 1; k < row; k++) {
            if (dp[k][j] != val) return false;
        }

        for (int k = j + 1; k < col; k++) {
            if (dp[i][k] != val) return false;
        }
        return true;
    }
}
